In recent years, the volume of color image data on the Internet has been explosively increasing. In particular, due to the increasing popularity of web sites, digital cameras, and online games, color image data have become a significant portion of the Internet traffic. On the other hand, access to color images through wireless channels or via low power, small devices is still time-consuming and inconvenient, which is mainly due to the limitations of image display device, storage, and transmission bandwidth has become a bottleneck for many multimedia applications—see, for example, J. Barrilleaux, R. Hinkle, and S. Wells, “Efficient vector quantization for color image encoding,” Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP '87, vol. 12, pp. 740-743, April 1987 (hereinafter “reference [1]”), M. T. Orchard and C. A. Bouman, “Color quantization of images,” Signal Processing, IEEE Transactions on, vol. 39, no. 12, pp. 2677-2690, December 1991 (hereinafter “reference [2]”), I. Ashdown, “Octree color quantization,” C/C++ Users Journal, vol. 13, no. 3, pp. 31-43, 1994 (hereinafter “reference [3]”), X. Wu, “Yiq vector quantization in a new color palette architecture,” IEEE Trans. on Image Processing, vol. 5, no. 2, pp. 321-329, 1996 (hereinafter “reference [4]”), L. Velho, J. Gomes, and M. V. R. Sobreiro, “Color image quantization by pairwise clustering,” Proc. Tenth Brazilian Symp. Comput. Graph. Image Process, L. H. de Figueiredo and M. L. Netto, Eds. Campos do Jordao, Spain, pp. 203-210, 1997 (hereinafter “reference [5]”) and S. Wan, P. Prusinkiewicz, and S. Wong, “Variance-based color image quantization for frame buffer display,” Res. Appl., vol. 15, pp. 52-58, 1990 (hereinafter “reference [6]”).
One way to alleviate the above limitations is to apply efficient color image encoding schemes which compress, optimize, or re-encode color images. A typical color image encoding scheme consists of a color palette, pixel mapping, and lossless code. The color palette acts as a vector quantization codebook, and is used to represent all colors in the original color image. The pixel mapping then maps each pixel in the image into an index corresponding to a color in the color palette. The pixel mapping could be either a hard decision pixel mapping for which the quantization of a RGB color vector into a color of the color palette is fixed and independent of the pixel location of the RGB color vector in the image once the color palette is given, or a soft decision pixel mapping for which a RGB color vector may be quantized into different colors of the color palette at different pixel locations. The index sequence resulting from the pixel mapping is finally encoded by a lossless code.
Previously, color palette design, pixel mapping, and coding were investigated separately. In the design of color palette and pixel mapping, the coding part is often ignored and the main objective is to reduce the quantization distortion, improve visual quality of quantized images, and decrease computational complexity. Several tree-structured splitting and merging color image quantization methods are proposed in the literature—see, for example, references [1] to [6]—to achieve, more or less, this objective. On the other hand, when coding is concerned, the color palette and pixel mapping are often assumed to be given, and the objective is to design efficient codes for the index sequence so as to reduce the compression rate. For instance, an algorithm for lossy compression in the LUV color space of color-quantized images was given in A. Zaccarin and B. Liu, “A novel approach for coding color quantized image,” Image Processing, IEEE Transactions on, vol. 2, no. 4, pp. 442-453, October 1993 (hereinafter “reference [7]”). Two heuristic solutions were proposed in N. D. Memon and A. Venkateswaran, “On ordering color maps for lossless predictive coding,” IEEE Transactions on Image Processing, vol. 5, no. 11, pp. 1522-1527, 1996 (hereinafter “reference [8]”), to reorder color maps prior to encoding the image by lossless predictive coding techniques. Based on a binary-tree structure and context-based entropy coding, a compression algorithm was proposed in X. Chen, S. Kwong, and J. fu Feng, “A new compression scheme for color-quantized images,” Circuits and Systems for Video Technology, IEEE Transactions on, vol. 12, no. 10, pp. 904-908, October 2002 (hereinafter “reference [9]”) to provide progressive coding of color-quantized images. In these algorithms, the compression efficiency is achieved at the expense of compressed bit streams incompatible with standard decoders such as the GIF/PNG decoder.